package KogSys;

public class DynamicProgramming {
	
	public static String viterbi(String r, String h){
		String[] ref = r.split(" ");
		String[] hyp = h.split(" ");
		int[][] m = new int[ref.length+1][hyp.length+1];
		for(int i=1; i<=ref.length; i++){
			m[i][0] = m[i-1][0] -2;
		}
		
		for(int i=1; i<=hyp.length; i++){
			m[0][i] = m[0][i-1] -3;
		}
		
		for(int i=1; i<=ref.length; i++){
			for(int j=1; j<=hyp.length; j++){
				if(ref[i-1].equals(hyp[j-1])){
					m[i][j] = Math.max(Math.max(m[i-1][j-1]+2, m[i-1][j]-2), m[i][j-1]-3);
				}else{
					m[i][j] = Math.max(Math.max(m[i-1][j-1]-1, m[i-1][j]-2), m[i][j-1]-3);
				}
			}
		}
		for(int i=0; i<=hyp.length; i++){
			for(int j=0; j<=ref.length; j++){
				System.out.print(m[j][i] + " ");
			}
			System.out.println("");
		}
		
		return way(m);
	}
	
	public static String way(int[][] ar){
		String res = "";
		int i= ar.length-1;
		int j = ar[0].length-1;
		int max;
		while(i!=0 && j!=0){
			if(i>0 || j>0){
				max = Math.max(Math.max(ar[i-1][j], ar[i][j-1]), ar[i-1][j-1]);
				if(ar[i-1][j] == max){
					res  = "delete " + res;
					i--;
				}else if(ar[i][j-1] == max){
					res = "insert " + res;
					j--;
				}else if(ar[i][j] > ar[i-1][j-1]){
					res = "match " + res;
					i--; j--;
				}else{
					res = "substitute " + res;
					i--; j--;
				}
			}else if(i==0){
				res = "insert " + res;
				j--;
			}else{
				res = "delete " + res;
				i--;
			}
		}
		return res;
	}
	
	public static void main(String[] args){
		String a = "Franz jagt im Taxi quer durch";
		String b = "Franz jagt quer durch Bayern";
		String c = "jagt Franz durch ganz Bayern im Taxi";
		String d = "jagt im Taxi Bayern";
		String e = "Den ganzen Tag quer durch Bayern jagt Franz";
		
		String ref = "Franz jagt im Taxi quer durch Bayern";
		System.out.println(viterbi(ref,a));
		System.out.println(viterbi(ref,b));
		System.out.println(viterbi(ref,c));
		System.out.println(viterbi(ref,d));
		System.out.println(viterbi(ref,e));
	}
}
